package com.interview;

public class Backpack {
    public static void main(String[] args) {
        // https://leetcode-cn.com/problems/coin-change/solution/yi-bian-jiu-dong-zhi-bei-bao-wen-ti-by-christmas_w/
        int[] w = {3, 5, 7};
        int[] val = {10, 20, 25};
        int m = 10; //背包的容量
        int res = new Backpack().backpack01(w, val, m);
        System.out.println(res);
        int res2 = new Backpack().backpackRepeatable(w, val, m);
        System.out.println(res2);
    }

    public int backpack01(int[] w, int[] val, int m){
        //v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
        int n = val.length; //物品的个数
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (w[i - 1] > j) {
                    // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
                    // 装不下
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //因为我们的i 从1开始的， 因此公式需要调整
                    dp[i][j] = Math.max(val[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j]);
                }
            }
        }
        //输出一下v 看看目前的情况
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return dp[n][m];
    }

    public int backpackRepeatable(int[] w, int[] val, int m){
        //v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
        int n = val.length; //物品的个数
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (w[i - 1] > j) {
                    // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
                    // 装不下
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //因为我们的i 从1开始的， 因此公式需要调整
                    //唯一不同的地方
                    dp[i][j] = Math.max(val[i - 1] + dp[i][j - w[i - 1]], dp[i - 1][j]);
                }
            }
        }
        //输出一下v 看看目前的情况
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return dp[n][m];
    }
}